#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
using namespace std;
char* my_strstr(const char* text,const char* pattern) {
	char* t = (char*)text, * p = (char*)pattern;
	int tsz = strlen(t), psz = strlen(p), rule = 0, i = 1;
	vector<int> prefix(psz, 0);
	while (i < psz) {
		if (p[rule] == p[i]) {
			prefix[i] = rule + 1;
			rule++;
			i++;
		}else{
			if (rule == 0) {
				prefix[i] = 0;
				i++;
			}
			else rule = prefix[rule - 1];
		}
	}
	i = 0, rule = 0;
	while (i < tsz) {
		if (t[i] == p[rule]) {
			rule++;
			i++;
		}
		else {
			if (rule == 0) i++;
			else rule = prefix[rule - 1];
		}
		if (rule == psz)return (char*)text + i - psz;
	}
	return NULL;
}
int main() {
	char ask[100] = "kyfaagsaf";
	char ax[] = "faag";
	cout << my_strstr(ask, ax) << endl;

	return 0;
}